/**
 * 深度优先实现方式
 */

window.SPACE = 0;

/**
 * 创建一个二维数组，并打乱顺序
 */
function createAry(cols, rows, seeds) {
    if (cols * rows % 2 == 1) cols ++;
    let a = new Array(rows + 2);
    let ans = 0;
    for (let i=0;i<a.length;i++) {
        a[i] = new Array(cols + 2);
        for (let j=0;j<a[i].length;j++) {
            if (i * j == 0 || i == a.length - 1 || j == a[0].length - 1) {
                a[i][j] = SPACE;
            } else {
                a[i][j] = seeds[ans++ % seeds.length];
                let rndx = parseInt(Math.random() * i) + 1;
                let rndy = parseInt(Math.random() * j) + 1;
                let tmp = a[i][j];
                a[i][j] = a[rndx][rndy];
                a[rndx][rndy] = tmp;
            }
        }
    }
    return a;
}
var found = false;
function disappear(a, x0, y0, targetx, targety) {
    if (a[x0][y0] === SPACE || a[targetx][targety] === SPACE
        || a[x0][y0] !== a[targetx][targety]
        || (x0 === targetx && y0 === targety)) {
        return false;
    }
    found = false;
    let result = null;
    dfs(a, { x:x0, y:y0, pre:null, zCount:0 }, {}, targetx, targety, (res) => {
        result = res;
        if (res) {
            a[x0][y0] = SPACE;
            a[targetx][targety] = SPACE;
        }
    });
    return result;
}
// 深搜核心算法
function dfs(a, node, flags, targetx, targety, callback) {
    if (found) return;
    const d = [{x:-1,y:0},{x:0,y:-1},{x:1,y:0},{x:0,y:1}];
    for (let i=0;i<d.length;i++) {
        let newNode = { x: node.x + d[i].x, y: node.y + d[i].y, pre: node, zCount: node.zCount || 0 };
        if (flags[newNode.x + '_' + newNode.y] || newNode.x < 0 || newNode.y < 0 || newNode.x >= a.length || newNode.y >= a[0].length) continue;
        if (newNode.pre.pre && newNode.pre.pre.x !== newNode.x && newNode.pre.pre.y !== newNode.y) {
            newNode.zCount ++;
        }
        if (newNode.zCount > 2) continue; // 如果折点大于2就不再继续搜
        if (newNode.x === targetx && newNode.y === targety) { // 如果找到目标位置
            if (a[newNode.x][newNode.y] === a[targetx][targety]) { // 如果相等
                callback(newNode); // 回调
                found = true;
            } else {
                callback(null);
                found = false;
            }
            return;
        }
        if (a[newNode.x][newNode.y] === SPACE) {
            flags[newNode.x + '_' + newNode.y] = true; // 标记
            if (animateList && !found) { /*此语句仅用于演示模式*/
                animateList.push({...newNode, type:'+'});
            }
            dfs(a, newNode, flags, targetx, targety, callback); // 搜索
            if (animateList && !found) { /*此语句仅用于演示模式*/
                animateList.push({...newNode, type:'-'});
            }
            flags[newNode.x + '_' + newNode.y] = false; // 回溯
        }
    }
}